# -*- coding: utf-8 -*-
# @Author: shj
# @Date: 2020-04-10 18:11:55
# @LastEditTime: 2020-04-10 19:10:54
# @LastEditors: shj
# @Description: 分治法例子：快速排序
# @FilePath: /python3/algorithms/Divide_and_conquer.py
'''
分治法 - 把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到可以直接求解的程度，最后将子问题的解进行合并得到原问题的解。

快速排序 - 选择枢轴对元素进行划分，左边都比枢轴小右边都比枢轴大

该算法的实现可分为以下几步：

1. 在数组中选一个基准数（通常为数组第一个）；

2. 将数组中小于基准数的数据移到基准数左边，大于或等于基准数的移到右边；

3. 对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。

一趟快速排序的算法是：  
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；  
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；  
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

从上述描述中可以看出，用递归可以很简单的实现算法
'''


def quick_sort(sort_list, low, high):
    '''快速排序'''
    # 递归出口：只有一个元素时，直接返回，不用排序
    if low >= high:
        return sort_list
    # 初始化，设置枢纽flag，低位移动指针i，高位移动指针j
    flag, i, j = sort_list[low], low, high
    # 循环判断，直到高低位移动指针相撞
    while i < j:
        # 这里特别注意：先从设置枢纽的反向进行判断，否则会出错
        # 例如：左侧设置枢纽，先从右侧进行判断并移动指针
        # 当高低位未相遇：高位指针持续低移，直到遇见小于枢纽的值(相等时不动)
        while i < j and sort_list[j] >= flag:
            j -= 1
        # 当高低位未相遇：低位指针持续高移，直到遇见大于枢纽的值(相等时不动)
        while i < j and sort_list[i] <= flag:
            i += 1
        # 将低位大于枢纽的值与高位小于枢纽的值互换
        sort_list[i], sort_list[j] = sort_list[j], sort_list[i]
    # 将枢纽值放入分界点（高低位指针相遇处）
    sort_list[low] = sort_list[i]
    sort_list[i] = flag
    # 递归排序左侧
    quick_sort(sort_list, low, i - 1)
    # 递归排序右侧
    quick_sort(sort_list, i + 1, high)
    # 返回排好序的列表
    return sort_list


# 示例
nosort_list = [2, 3, 5, 7, 1, 4, 6, 15, 5, 2, 7, 9, 10, 15, 9, 17, 12]
print(quick_sort(nosort_list, 0, len(nosort_list) - 1))
'''
# 另一种递归方式
def partition(array, l, r):
    x = array[r]
    i = l - 1
    # 主要区别在这里：
    # 用一个for循环进行大小判断，相比多个while要节省运行时间
    for j in range(l, r):
        # 右侧设枢纽，从左侧开始判断，将小于枢纽的值全部放左侧
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[r] = array[r], array[i + 1]
    # 返回的是枢纽的坐标
    return i + 1


def quick_sort(array, l, r):
    if l < r:
        q = partition(array, l, r)
        quick_sort(array, l, q - 1)
        quick_sort(array, q + 1, r)
'''